//https://www.nowcoder.com/practice/fd55637d3f24484e96dad9e992d3f62e?tpId=230&tqId=2032484&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
#include <iostream>

using namespace std;
const int N = 1010;
int n, V, v[N], w[N];
int dp1[N][N];
int dp2[N][N];
int main() {
    // 读⼊数据
    cin >>  n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    //解决第一问
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= V; j++) {
            dp1[i][j] = dp1[i - 1][j];
            if (j >= v[i])
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][j - v[i]] + w[i]);
        }
    cout << dp1[n][V] << endl;

    //解决第二问
    for (int j = 1; j <= V; j++) dp2[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= V; j++) 
        { 
            dp2[i][j] = dp2[i - 1][j];
            if (j >= v[i] && dp2[i - 1][j - v[i]] != -1)
                dp2[i][j] = max(dp2[i][j], dp2[i - 1][j - v[i]] + w[i]);
        }
    cout << (dp2[n][V] == -1 ? 0 : dp2[n][V]) << endl;


    return 0;
}